\(~\)

Introduction

For my Data Analytics Project, my task is to build at least two recommendation systems using a Musical Instruments dataset and to use them to predict the product ratings for some users based on other users’ ratings. Two datasets have been given to me: the first one contains information about user preferences on musical instruments (ratings); the second one contains information about each rated item (metadata).

My main tasks are:

Overview

A recommendation system is an information filtering system that aims to predict user responses to option; in particular, it tries to predict the user preference or rating of an item. It can be used to offer users custom suggestions about which items they might like, based on similarity between other users or other items, or based on a custom “profile” of the user or of the item.

The recommendation systems can be classified in two main groups:

Exploration and description of data

First, I import all the packages that I need in order to handle the dataset.

library(jsonlite)
library(ggplot2)
library(lubridate)
library(scales)
library(formattable)
library(recommenderlab)
library(data.table)
library(Matrix)

Then, I start by importing the datasets; to do this, I convert the .csv file containing the ratings and the .json file containing the metadata into two dataframes.

ds = read.csv(file = "ratings.csv")
colnames(ds) = c("user", "item", "rating", "timestamp")
ds['timestamp'] = as.POSIXct(ds[,'timestamp'], origin="1970-01-01")
json = readLines("new_meta_Musical_Instruments.json")
metadata = fromJSON(json)

In order to have an idea of the type of data I’m going to work with, I visualize the head and a summary of data.

head(ds)
summary(ds)
             user                item            rating        timestamp                  
 A2PAD826IH1HFE:   483   B000ULAP4U:  3523   Min.   :1.000   Min.   :1998-04-25 02:00:00  
 A2AIMXT9PLAM12:   463   B003VWJ2K8:  2275   1st Qu.:4.000   1st Qu.:2011-12-28 01:00:00  
 A2NYK9KWFMJV4Y:   454   B003VWKPHC:  1603   Median :5.000   Median :2013-03-27 01:00:00  
 A33GGROUQRQZS :   154   B001MSS6CS:  1420   Mean   :4.244   Mean   :2012-08-10 03:05:21  
 A2PR6NXG0PA3KY:   135   B00FPPQYXM:  1287   3rd Qu.:5.000   3rd Qu.:2013-12-28 01:00:00  
 ALAJL3S09HBS7 :   126   1417030321:  1218   Max.   :5.000   Max.   :2014-07-23 02:00:00  
 (Other)       :498360   (Other)   :488849                                                
cat("Rating standard deviation:", sd(ds$rating))
Rating standard deviation: 1.203374
# head(metadata)                # I leave this two lines commented because
# summary(metadata)             the output is too big for the report

The csv dataset contains 4 attributes, which are user, item, rating and timestamp, and 500,175 observations, each one representing an item’s rating gaved by a user. This is the most interesting dataset, since it relates users and items by the corresponding rating, therefore I will work mostly on this data.

The json dataset contains 9 attributes, which are asin (item id), title, price, imUrl, salesRank, categories, description, related and brand, and 84,901 observations, each one representing the metadata of one item. Some attributes in turn contain a list of elements, like salesRank and categories. After I deeply explored this dataset, I realised that it doesn’t contain very interesting data for my purpose, furthermore more than a half of the metadata values are NA and can’t be used (I will show that later).

In general, the number of distinct users is 339,231, while the number of distinct items that have been rated is 83,045.

\(~\)

Back to the ratings dataset, the summary already give us some standard descriptive statistics: the min and max functions let us know that the ratings go from 1 to 5; the mean equal to 4.244 tells us that, in general, the users have rated the items with very high grades, mostly with 5; also the low standard deviation indicates that lots of rating values are close to the mean.

This observation is also confirmed by the quartiles and the median. Indeed, the first quartile is already equal to 4, which is a really high number for data that takes values up to 5 - since it represents the middle number between the minimum value and the median. The same observation can be done for the median, that is equal to 5, i.e. the maximum value.

The information about timestamps given by the summary shows that the ratings are related to the years 1998 to 2014, but the majority is between 2011 and 2014.

\(~\)

After I had an overview of data, I immediately check for the presence of NA values, that could create problems when computing statistics on data and that, if present, have to be substituted with real values or omitted.

t_count = sum(is.na(ds))
is_na = if (t_count > 0) 'The ratings dataset does contain NA values' else 'The ratings dataset does not contain NA values'
cat(is_na)
The ratings dataset does not contain NA values
t_count = sum(is.na(metadata))
is_na = if (t_count > 0) 'The metadata dataset does contain NA values' else 'The metadata dataset does not contain NA values'
cat(is_na)
The metadata dataset does contain NA values

As I already mentioned before, while the ratings dataset does not contain NA values, the metadata dataset contains NA values, but in order to find all of them, we need to search also inside the lists of some attribute. To do so, I will check only the attributes that could be useful for the construction of a recommendation system (for example, I discard the description in advance).

# -- asin NA values check
    t_count = sum(is.na(metadata$asin))
    is_na = if (t_count > 0) 'The attribute asin does contain NA values' else 'The attribute asin does not contain NA values'
    cat(is_na, "\n")
The attribute asin does not contain NA values 
# -- salesRank NA values check
    # print(names(metadata$salesRank))          # print all the different categories of sales rank
    t_count = sum(is.na(metadata$salesRank$`Musical Instruments`))
    is_na = if (t_count > 0) 'The attribute Musical Instruments salesRank does contain NA values' else 'The attribute Musical Instruments salesRank does not contain NA values'
    cat(is_na, "->", t_count, "over", length(metadata$salesRank$`Musical Instruments`), "\n")
The attribute Musical Instruments salesRank does contain NA values -> 21714 over 84901 
# -- related NA values check
    new_related = metadata$related
    new_related[new_related == "NULL"] = NA             # convert NULL values in NA values
    n_values = nrow(metadata$related)*ncol(metadata$related)
    t_count = sum(is.na(unlist(new_related)))
    is_na = if (t_count > 0) 'The attribute related does contain NA values' else 'The attribute related does not contain NA values'
    cat(is_na, "->", t_count, "over", n_values, "\n")
The attribute related does contain NA values -> 188242 over 339604 
# -- brand NA values check
    n_values = length(metadata$brand)
    t_count = sum(is.na(metadata$brand))
    is_na = if (t_count > 0) 'The attribute brand does contain NA values' else 'The attribute brand does not contain NA values'
    cat(is_na, "->", t_count, "over", n_values, "\n")
The attribute brand does contain NA values -> 50387 over 84901 
# -- price NA values check
    n_values = length(metadata$price)
    t_count = sum(is.na(metadata$price))
    is_na = if (t_count > 0) 'The attribute price does contain NA values' else 'The attribute price does not contain NA values'
    cat(is_na, "->", t_count, "over", n_values)
The attribute price does contain NA values -> 15831 over 84901

Unfortunately, the number of NA values for Musical Instruments sales rank, related and brand is too high: in the first attribute a quarter of the values are missing, while in the other two more than an half of the values are NA. For this reason, it would be pointless to try to substitute the NA values with the mean of the present values, or to delete the data with NA values from the dataset. Therefore, I think in this case it is appropriate not to consider these attributes for the development of the recommendation systems.

However, as regards the number of NA values for the attribute price, it is borderline and I will decide later if it could be useful to analyse it.

\(~\)

To be shure that I can use all the items for the construction of my recommendation system, I check if all of them contain the category “Musical Instruments” among the categories.

# -- Print unique possible values for attribute categories
    # print(unique(unlist(metadata$categories)))
# -- All the lists internal to categories are flatten
    for (i in length(metadata$categories)) {
        temp = unlist(metadata$categories[i])
        metadata$categories[[i]] = temp
    }
# -- Check if all the items have "Musical Instruments" as one of their categories
    check = metadata[is.element("Musical Instruments", metadata$categories)]
    cat("Items of the dataframe that have 'Musical Instruments' in their categories:", nrow(check), "over", nrow(metadata))
Items of the dataframe that have 'Musical Instruments' in their categories: 84901 over 84901

Representation and visualization of data

In order to explore and describe data, I also use some graphic representations, that can show the data distribution and some of its characteristics.

I start by blotting an histogram showing the relative frequencies of ratings.

ggplot(data=ds, aes(x=rating, fill=rating)) +
    geom_bar(fill="steelblue", aes(y=..count../sum(..count..))) +
        scale_y_continuous(limits = c(0,1)) +
        labs(title = "Histogram of ratings", x = "Rating", y = "Relative frequency") +
        theme_minimal()

fr = prop.table(table(ds$rating))
fr = percent(fr)
print(fr)

    1     2     3     4     5 
 7.0%  4.5%  7.7% 18.7% 62.1%

The figure shows that there is a large majority of high ratings: more than a half of the ratings are equal to 5. This confirms the previous considerations resulting from the descriptive statistics.

\(~\)

The following plot shows the trend of the rating’s mean as the years passed.

m_by_y = aggregate(ds$rating, list(year(ds$timestamp)), mean)
colnames(m_by_y) = c("years", "means")
# print(m_by_y)
ggplot(data=m_by_y, aes(x=years, y=means, fill=years)) +
    geom_bar(stat = "identity", fill="steelblue") +
        scale_x_continuous(limits = c(min(m_by_y$years)-1,max(m_by_y$years)+1), 
                                             breaks = c(min(m_by_y$years),2000,2005,2010,max(m_by_y$years))) +
        scale_y_continuous(limits = c(0,5)) +
        geom_hline(aes(yintercept=mean(m_by_y$means), linetype = "Total mean"), colour="darkblue") +
        scale_linetype_manual(name = "Legend", values = c(2, 2)) +
        labs(title = "Trend of rating's mean based on years", x = "Years", y = "Rating's mean") +
        theme_minimal()

\(~\)

Since the number of distinct items that have been rated is very big (83,045), in order to visualize the distribution of rating with respect to the items I decided to represent the items’ ratings in the plot by 17 ordered groups of 4885 items each, so that a clearer graph is obtained. The figure shows the rating, aggregated by mean, for each group of items.

m_by_y = aggregate(ds$rating, list(ds$item), mean)
colnames(m_by_y) = c("items", "means")
m_by_y = m_by_y[with(m_by_y, order(m_by_y$means, decreasing = TRUE)),]
groups = c(rep("G", 17))
groups = paste(groups, c(1:17), sep = "")
v = c()
i = 1
N = 4885
for (k in 1:17) {
    v[k] = mean(m_by_y$means[i:(i+N-1)])
    i = i+N
}
df = data.frame("groups" = groups,
                                 "means" = v,
                                 stringsAsFactors = FALSE)
df$groups <- factor(df$groups, levels = df$groups)
ggplot(data=df, aes(x=groups, y=means, fill=groups)) +
    geom_bar(stat = "identity") +
        scale_y_continuous(limits = c(0,5)) +
        geom_hline(aes(yintercept=mean(m_by_y$means), linetype = "Total mean"), colour="darkblue") +
        scale_linetype_manual(name = "Legend", values = c(2, 2)) +
        scale_fill_manual(values=c(rep("steelblue", 17))) +
        guides(fill=FALSE) +
        labs(title = "Rating's mean with respect to items", x = "Items", y = "Rating's mean") +
        theme_minimal()

It could be also interesting to see the relation between the ratings and the prices of items. To obtain it, I discard from the metadata dataset all the items that haven’t been rated and from both the datasets all the items that have the price value equal to NA. Then, I compute the correlation matrix between the ratings and the prices to check for the presence of a linear correlation between data and I also plot the distribution of the two related variable to have an overall view and to check for the presence of non-linear relations.

# -- Discard from metadata all the items that haven't been rated
metadata = metadata[is.element(metadata$asin, ds$item),]
# -- Discard from both the dataset all the items that have the price value equal to NA
metadata_price = metadata[!is.na(metadata$price),]
metadata_price = data.frame("asin" = metadata_price$asin,
                                                        "price" = metadata_price$price,
                                                        stringsAsFactors = FALSE)
metadata_price = metadata_price[order(metadata_price$asin),]
ds_price = ds[is.element(ds$item, metadata_price$asin),]
ds_price = aggregate(ds_price$rating, by = list(ds_price$item), mean)
ds_price = ds_price[order(ds_price$Group.1),]
ds_price = data.frame("item" = ds_price$Group.1,
                                            "price" = metadata_price$price,
                                            "rating" = ds_price$x,
                                            stringsAsFactors = FALSE)
means = aggregate(ds_price$price, by = list(ds_price$rating), mean)
names(means) = c("rating", "price")
cormat = round(cor(means), 4)
cormat
       rating  price
rating 1.0000 0.0097
price  0.0097 1.0000
ggplot(data = means, aes(x = rating, y = price)) + 
  geom_point(color='steelblue') +
    theme_minimal()

The resulting correlation matrix shows that there is no linear correlation between the variables rating and price, as the correlation value is very close to zero. However, from the graph we can deduct the presence of a non-linear relation between the two variables: as the ratings grows, also the prices grows, but it is also true that a lot of items with high rating have a very low price and the higher the rating, the denser is the “cloud” of low prices.

Pre-processing of data

In order to create the recommendation systems, I will use only the ratings dataset, because the metadata dataset contains too many NA values. I remove the attribute timestamp from the ratings dataset since I don’t need it.

rating = ds[,c("user", "item", "rating")]

I will use a subset of users and items to create the recommendation systems for two reasons:

# -- Check if each user rated each items only once
# length(unique(c(ds$user, ds$item)))           # number of distinct couples "user, item" equals number of distinct users
old_nrow = nrow(rating)
# -- Mean of the number of ratings received by each item
item_rating = aggregate(rating$rating, by = list(rating$item), length)
names(item_rating) = c("item", "nrating")
item_mean = mean(item_rating$nrating)           # item_mean = 6.023
old_nrow_item = nrow(item_rating)
# -- Items filtering
item_rating = item_rating[item_rating$nrating >= 20,]
rating = rating[is.element(rating$item, item_rating$item),]
# -- Mean of the number of ratings done by each user
user_rating = aggregate(rating$rating, by = list(rating$user), length)
names(user_rating) = c("user", "nrating")
user_mean = mean(user_rating$nrating)               # user_mean = 1.47
old_nrow_user = nrow(user_rating)
# -- Users filtering
user_rating = user_rating[user_rating$nrating >= 6,]
rating = rating[is.element(rating$user, user_rating$user),]
cat("Subset of rating -> ", "Total number of ratings:", nrow(rating), "over", old_nrow, "\n",
        "\t\t\t\t\t", "Number of distinct users:", length(unique(rating$user)), "over", old_nrow_user, "\n",
        "\t\t\t\t\t", "Number of distinct items:", length(unique(rating$item)), "over", old_nrow_item, "\n")
Subset of rating ->  Total number of ratings: 15864 over 500175 
                     Number of distinct users: 1840 over 206538 
                     Number of distinct items: 3147 over 83045

The resulting dataset contains 15,864 ratings, 1,840 distinct users and 3,147 distinct items. This will be the dataset on which I will work from now on.

Recommendation systems

In order to build the two recommendation systems required by the project, I’m going to use collaborative filtering (CF) in both cases: one of them will make use of the user-based collaborative filtering (UBCF), the other will make use of the item-based collaborative filtering (IBCF).

Collaborative filtering is an algorithm that uses given rating data by many users for many items as the basis for predicting missing ratings or for creating a list of items with the top-N items to recommend to a given user, called the active user. The data are organized in a \(m \times n\) user-item matrix, called utility matrix or sparse matrix, where each row represents a user and each column represents an item. Into each user-item cell it is stored the rating of that user for that item. Usually, the utility matrix is very sparse, because only a small fraction of ratings are known, so most of the cells of the matrix contain NA values.

Two of the main categories of CF algoritms are the user-based collaborative filtering and the item-based collaborative filtering. The UBCF algorithms bases the recommendations on the similarity between users: the assumption is that users with similar preferences will rate items similarly. Each user is represented by his row of ratings in the utility matrix, so, in order to compute the similarity between users, we need to apply a similarity measure (for istance, the cosine similarity) between the row of the active user and all the other rows. In this way, we can find the most similar users and use their ratings in two ways:

The IBCF algorithms bases the recommendations on the similarity between items: the assumption is that users will prefer items that are similar to other items they like. Each item is represented by his column of ratings in the utility matrix, so, in order to compute the similarity between items, we need to apply a similarity measure (for istance, the cosine similarity) between all the columns of the utility matrix. In this way, we can build a \(n \times n\) item-item similarity matrix containing the similarity values for each items couple. To reduce the dimensionality of the similarity matrix, instead we could build a \(n \times k\) item-item similarity matrix containing, for each item, the similarity values of only the k most similar items. From the similarity matrix, we can use the items that are the most similar to the best rated items of the active user in order to obtain:

\(~\)

In order to build the two recomendation systems, I’m going to use the recommenderlab library, which provides several algorithms for this tipe of task that are already implemented.

First, I need to create the utility matrix from the ratings dataset. The function dcast is perfect for this purpose: it simply stores the users as rows’ indices, the items as columns’ indices and the ratings as values inside the user-item cells.

utility_matrix = dcast(rating, formula = user~item, value.var = 'rating')
n_values = nrow(utility_matrix)*(ncol(utility_matrix)-1)        # the first column contains users'ids
real_values = sum(!is.na(utility_matrix[,-1]))
cat("Number of real rating values:", real_values, "over", n_values)
Number of real rating values: 15864 over 5790480

The utility matrix contains 5,790,480 values, of which only 15,864 are real ratings and the others are missing values (NA).

Before working on the utility matrix, I need to convert it into matrix type (the function dcast returns a list) in order to be able to transform it in a realRatingMatrix to handle it through the recommentderlab library.

m = as.matrix(utility_matrix[,-1])
rownames(m) = utility_matrix[,1]
# print(m[1:10,1:8])
utility_m <- as(m, "realRatingMatrix")
utility_m
1840 x 3147 rating matrix of class ‘realRatingMatrix’ with 15864 ratings.

Before building the actual recommendation systems, I create an evaluation scheme that determines what and how data is used for training and testing and that allows me to evaluate the two models at the end. The division in training set and test set makes it possible to predict the ratings of the users in the test set using the training set. Through the evaluation scheme, I split the dataset using 75% of users for the training set and 25% for the test set, I consider good ratings only the ratings equal to 5 (anyway, more than a half of the ratings are equal to 5) and I set to 4 the value of given ratings, so that in the test set each user have 4 ratings given and the recommendation systems have to predict the others that are missing.

e = evaluationScheme(utility_m, method = "split", train = 0.75, given = 4, goodRating = 5)
e
Evaluation scheme with 4 items given
Method: ‘split’ with 1 run(s).
Training set proportion: 0.750
Good ratings: >=5.000000
Data set: 1840 x 3147 rating matrix of class ‘realRatingMatrix’ with 15864 ratings.

After that, I create the two recommendation systems with the function Recommender, where I can set the training set as the data that it has to use to build the recommendation system and the method, depending on whether it has to use the UBCF or the IBCF. Then, I use the created Recommenders in order to predict the missing ratings in the test set through the function predict.

# --- Recommendation system using UBCF
rUBCF = Recommender(getData(e, "train"), method = "UBCF")
rUBCF
Recommender of type ‘UBCF’ for ‘realRatingMatrix’ 
learned using 1380 users.
pUBCF = predict(rUBCF, getData(e, "known"), type = "ratings")
pUBCF
460 x 3147 rating matrix of class ‘realRatingMatrix’ with 902041 ratings.
# --- Recommendation system using IBCF
rIBCF = Recommender(getData(e, "train"), method = "IBCF")
rIBCF
Recommender of type ‘IBCF’ for ‘realRatingMatrix’ 
learned using 1380 users.
pIBCF = predict(rIBCF, getData(e, "known"), type = "ratings")
pIBCF
460 x 3147 rating matrix of class ‘realRatingMatrix’ with 57147 ratings.

Finally, I evaluate the predictions of the two recommendation systems by comparing their accuracy through an evaluation matrix. The matrix contains, for each model, the root-mean-square error (RMSE), that is the square root of the mean square error, the mean squared error (MSE), that measures the average of the squares of the differences between predicted values and observed values, and the mean absolute error (MAE), that represents the average absolute difference between predicted values and observed values.

# Error between prediction and unknown part of the test data
error = rbind(UBCF = calcPredictionAccuracy(pUBCF, getData(e, "unknown")),
                            IBCF = calcPredictionAccuracy(pIBCF, getData(e, "unknown")))
error
          RMSE       MSE       MAE
UBCF 0.9631215 0.9276031 0.6462931
IBCF 1.3906379 1.9338738 0.9206462

I tried different configurations for the data filtering, lowering or rasing the number of users and items selected to form the dataset: obviously, the higher the minimum number of ratings for each user and item, the lower the error of the predictions. In general, the UBCF works better than the IBCF with every configuration I tried, since all the three measures of error are higher in the UBCF than in the IBCF.

LS0tCnRpdGxlOiAiRGF0YSBBbmFseXRpY3MgUHJvamVjdCIKc3VidGl0bGU6ICIxOSAtIE11c2ljYWwgSW5zdHJ1bWVudHMgUmVjb21tZW5kYXRpb24iCmF1dGhvcjogIkFsZXNzaWEgUnVnZ2VyaSIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKICBwZGZfZG9jdW1lbnQ6IGRlZmF1bHQKLS0tCgokfiQKCiMjIEludHJvZHVjdGlvbgoKRm9yIG15IERhdGEgQW5hbHl0aWNzIFByb2plY3QsIG15IHRhc2sgaXMgdG8gYnVpbGQgYXQgbGVhc3QgdHdvIHJlY29tbWVuZGF0aW9uIHN5c3RlbXMgdXNpbmcgYSBNdXNpY2FsIEluc3RydW1lbnRzIGRhdGFzZXQgYW5kIHRvIHVzZSB0aGVtIHRvIHByZWRpY3QgdGhlIHByb2R1Y3QgcmF0aW5ncyBmb3Igc29tZSB1c2VycyBiYXNlZCBvbiBvdGhlciB1c2Vyc+KAmSByYXRpbmdzLiBUd28gZGF0YXNldHMgaGF2ZSBiZWVuIGdpdmVuIHRvIG1lOiB0aGUgZmlyc3Qgb25lIGNvbnRhaW5zIGluZm9ybWF0aW9uIGFib3V0IHVzZXIgcHJlZmVyZW5jZXMgb24gbXVzaWNhbCBpbnN0cnVtZW50cyAocmF0aW5ncyk7IHRoZSBzZWNvbmQgb25lIGNvbnRhaW5zIGluZm9ybWF0aW9uIGFib3V0IGVhY2ggcmF0ZWQgaXRlbSAobWV0YWRhdGEpLgoKTXkgbWFpbiB0YXNrcyBhcmU6CgoqIEV4cGxvcmUgYW5kIGRlc2NyaWJlIHRoZSBkYXRhIHRocm91Z2ggc29tZSBzdGFuZGFyZCBkZXNjcmlwdGl2ZSBzdGF0aXN0aWNzIGFuZCBzb21lIGdyYXBoczsKKiBQcmUtcHJvY2VzcyB0aGUgZGF0YTsKKiBCdWlsZCBhdCBsZWFzdCB0d28gcmVjb21tZW5kYXRpb24gc3lzdGVtcyBmb3IgbXVzaWNhbCBpbnN0cnVtZW50cyByYXRpbmdzOwoqIFNwbGl0IHRoZSBkYXRhIGludG8gdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cyBhbmQgcHJlZGljdCB0aGUgdmFyaWFibGUgJ3JhdGluZycgaW4gdGhlIHRlc3Qgc2V0OwoqIEV2YWx1YXRlIGFuZCBjb21wYXJlIHRoZSBhY2N1cmFjeSBvZiB0aGUgZGlmZmVyZW50IG1vZGVscy4KCgojIyBPdmVydmlldwoKQSByZWNvbW1lbmRhdGlvbiBzeXN0ZW0gaXMgYW4gaW5mb3JtYXRpb24gZmlsdGVyaW5nIHN5c3RlbSB0aGF0IGFpbXMgdG8gcHJlZGljdCB1c2VyIHJlc3BvbnNlcyB0byBvcHRpb247IGluIHBhcnRpY3VsYXIsIGl0IHRyaWVzIHRvIHByZWRpY3QgdGhlIHVzZXIgcHJlZmVyZW5jZSBvciByYXRpbmcgb2YgYW4gaXRlbS4gSXQgY2FuIGJlIHVzZWQgdG8gb2ZmZXIgdXNlcnMgY3VzdG9tIHN1Z2dlc3Rpb25zIGFib3V0IHdoaWNoIGl0ZW1zIHRoZXkgbWlnaHQgbGlrZSwgYmFzZWQgb24gc2ltaWxhcml0eSBiZXR3ZWVuIG90aGVyIHVzZXJzIG9yIG90aGVyIGl0ZW1zLCBvciBiYXNlZCBvbiBhIGN1c3RvbSAicHJvZmlsZSIgb2YgdGhlIHVzZXIgb3Igb2YgdGhlIGl0ZW0uCgpUaGUgcmVjb21tZW5kYXRpb24gc3lzdGVtcyBjYW4gYmUgY2xhc3NpZmllZCBpbiB0d28gbWFpbiBncm91cHM6CgoqIENvbnRlbnQtYmFzZWQgc3lzdGVtczogdGhleSBiYXNlIHRoZWlyIHN1Z2dlc3Rpb25zIG9uIHRoZSBwcm9wZXJ0aWVzIG9mIHRoZSBpdGVtcyByZWNvbW1lbmRlZDsKKiBDb2xsYWJvcmF0aXZlIGZpbHRlcmluZyBzeXN0ZW1zOiB0aGV5IHJlY29tbWVuZCBpdGVtcyBiYXNlZCBvbiBzaW1pbGFyaXR5IGJldHdlZW4gdXNlcnMgb3IgYmV0d2VlbiBpdGVtcy4KCgojIyBFeHBsb3JhdGlvbiBhbmQgZGVzY3JpcHRpb24gb2YgZGF0YQoKRmlyc3QsIEkgaW1wb3J0IGFsbCB0aGUgcGFja2FnZXMgdGhhdCBJIG5lZWQgaW4gb3JkZXIgdG8gaGFuZGxlIHRoZSBkYXRhc2V0LgpgYGB7ciBJbXBvcnQgcGFja2FnZXMsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoanNvbmxpdGUpCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShsdWJyaWRhdGUpCmxpYnJhcnkoc2NhbGVzKQpsaWJyYXJ5KGZvcm1hdHRhYmxlKQpsaWJyYXJ5KHJlY29tbWVuZGVybGFiKQpsaWJyYXJ5KGRhdGEudGFibGUpCmxpYnJhcnkoTWF0cml4KQpgYGAKClRoZW4sIEkgc3RhcnQgYnkgaW1wb3J0aW5nIHRoZSBkYXRhc2V0czsgdG8gZG8gdGhpcywgSSBjb252ZXJ0IHRoZSAuY3N2IGZpbGUgY29udGFpbmluZyB0aGUgcmF0aW5ncyBhbmQgdGhlIC5qc29uIGZpbGUgY29udGFpbmluZyB0aGUgbWV0YWRhdGEgaW50byB0d28gZGF0YWZyYW1lcy4KYGBge3IgSW1wb3J0IHJhdGluZ3N9CmRzID0gcmVhZC5jc3YoZmlsZSA9ICJyYXRpbmdzLmNzdiIpCmNvbG5hbWVzKGRzKSA9IGMoInVzZXIiLCAiaXRlbSIsICJyYXRpbmciLCAidGltZXN0YW1wIikKZHNbJ3RpbWVzdGFtcCddID0gYXMuUE9TSVhjdChkc1ssJ3RpbWVzdGFtcCddLCBvcmlnaW49IjE5NzAtMDEtMDEiKQpgYGAKCmBgYHtyIEltcG9ydCBtZXRhZGF0YX0KanNvbiA9IHJlYWRMaW5lcygibmV3X21ldGFfTXVzaWNhbF9JbnN0cnVtZW50cy5qc29uIikKbWV0YWRhdGEgPSBmcm9tSlNPTihqc29uKQpgYGAKCkluIG9yZGVyIHRvIGhhdmUgYW4gaWRlYSBvZiB0aGUgdHlwZSBvZiBkYXRhIEknbSBnb2luZyB0byB3b3JrIHdpdGgsIEkgdmlzdWFsaXplIHRoZSBoZWFkIGFuZCBhIHN1bW1hcnkgb2YgZGF0YS4KYGBge3IgSW5zcGVjdCByYXRpbmdzfQpoZWFkKGRzKQpzdW1tYXJ5KGRzKQpjYXQoIlJhdGluZyBzdGFuZGFyZCBkZXZpYXRpb246Iiwgc2QoZHMkcmF0aW5nKSkKIyBoZWFkKG1ldGFkYXRhKQkJCQkjIEkgbGVhdmUgdGhpcyB0d28gbGluZXMgY29tbWVudGVkIGJlY2F1c2UKIyBzdW1tYXJ5KG1ldGFkYXRhKQkJCQl0aGUgb3V0cHV0IGlzIHRvbyBiaWcgZm9yIHRoZSByZXBvcnQKYGBgCgpUaGUgYGNzdmAgZGF0YXNldCBjb250YWlucyA0IGF0dHJpYnV0ZXMsIHdoaWNoIGFyZSAqdXNlciosICppdGVtKiwgKnJhdGluZyogYW5kICp0aW1lc3RhbXAqLCBhbmQgNTAwLDE3NSBvYnNlcnZhdGlvbnMsIGVhY2ggb25lIHJlcHJlc2VudGluZyBhbiBpdGVtJ3MgcmF0aW5nIGdhdmVkIGJ5IGEgdXNlci4gVGhpcyBpcyB0aGUgbW9zdCBpbnRlcmVzdGluZyBkYXRhc2V0LCBzaW5jZSBpdCByZWxhdGVzIHVzZXJzIGFuZCBpdGVtcyBieSB0aGUgY29ycmVzcG9uZGluZyByYXRpbmcsIHRoZXJlZm9yZSBJIHdpbGwgd29yayBtb3N0bHkgb24gdGhpcyBkYXRhLgoKVGhlIGBqc29uYCBkYXRhc2V0IGNvbnRhaW5zIDkgYXR0cmlidXRlcywgd2hpY2ggYXJlICphc2luKiAoaXRlbSBpZCksICp0aXRsZSosICpwcmljZSosICppbVVybCosICpzYWxlc1JhbmsqLCAqY2F0ZWdvcmllcyosICpkZXNjcmlwdGlvbiosICpyZWxhdGVkKiBhbmQgKmJyYW5kKiwgYW5kIDg0LDkwMSBvYnNlcnZhdGlvbnMsIGVhY2ggb25lIHJlcHJlc2VudGluZyB0aGUgbWV0YWRhdGEgb2Ygb25lIGl0ZW0uIFNvbWUgYXR0cmlidXRlcyBpbiB0dXJuIGNvbnRhaW4gYSBsaXN0IG9mIGVsZW1lbnRzLCBsaWtlICpzYWxlc1JhbmsqIGFuZCAqY2F0ZWdvcmllcyouIEFmdGVyIEkgZGVlcGx5IGV4cGxvcmVkIHRoaXMgZGF0YXNldCwgSSByZWFsaXNlZCB0aGF0IGl0IGRvZXNuJ3QgY29udGFpbiB2ZXJ5IGludGVyZXN0aW5nIGRhdGEgZm9yIG15IHB1cnBvc2UsIGZ1cnRoZXJtb3JlIG1vcmUgdGhhbiBhIGhhbGYgb2YgdGhlIG1ldGFkYXRhIHZhbHVlcyBhcmUgTkEgYW5kIGNhbid0IGJlIHVzZWQgKEkgd2lsbCBzaG93IHRoYXQgbGF0ZXIpLgoKSW4gZ2VuZXJhbCwgdGhlIG51bWJlciBvZiBkaXN0aW5jdCB1c2VycyBpcyAzMzksMjMxLCB3aGlsZSB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IGl0ZW1zIHRoYXQgaGF2ZSBiZWVuIHJhdGVkIGlzIDgzLDA0NS4KCiR+JAoKQmFjayB0byB0aGUgcmF0aW5ncyBkYXRhc2V0LCB0aGUgc3VtbWFyeSBhbHJlYWR5IGdpdmUgdXMgc29tZSAqKnN0YW5kYXJkIGRlc2NyaXB0aXZlIHN0YXRpc3RpY3MqKjogdGhlIGBtaW5gIGFuZCBgbWF4YCBmdW5jdGlvbnMgbGV0IHVzIGtub3cgdGhhdCB0aGUgcmF0aW5ncyBnbyBmcm9tIDEgdG8gNTsgdGhlIGBtZWFuYCBlcXVhbCB0byA0LjI0NCB0ZWxscyB1cyB0aGF0LCBpbiBnZW5lcmFsLCB0aGUgdXNlcnMgaGF2ZSByYXRlZCB0aGUgaXRlbXMgd2l0aCB2ZXJ5IGhpZ2ggZ3JhZGVzLCBtb3N0bHkgd2l0aCA1OyBhbHNvIHRoZSBsb3cgYHN0YW5kYXJkIGRldmlhdGlvbmAgaW5kaWNhdGVzIHRoYXQgbG90cyBvZiByYXRpbmcgdmFsdWVzIGFyZSBjbG9zZSB0byB0aGUgbWVhbi4KClRoaXMgb2JzZXJ2YXRpb24gaXMgYWxzbyBjb25maXJtZWQgYnkgdGhlIGBxdWFydGlsZXNgIGFuZCB0aGUgYG1lZGlhbmAuIEluZGVlZCwgdGhlIGZpcnN0IHF1YXJ0aWxlIGlzIGFscmVhZHkgZXF1YWwgdG8gNCwgd2hpY2ggaXMgYSByZWFsbHkgaGlnaCBudW1iZXIgZm9yIGRhdGEgdGhhdCB0YWtlcyB2YWx1ZXMgdXAgdG8gNSAtIHNpbmNlIGl0IHJlcHJlc2VudHMgdGhlIG1pZGRsZSBudW1iZXIgYmV0d2VlbiB0aGUgbWluaW11bSB2YWx1ZSBhbmQgdGhlIG1lZGlhbi4gVGhlIHNhbWUgb2JzZXJ2YXRpb24gY2FuIGJlIGRvbmUgZm9yIHRoZSBtZWRpYW4sIHRoYXQgaXMgZXF1YWwgdG8gNSwgaS5lLiB0aGUgbWF4aW11bSB2YWx1ZS4KClRoZSBpbmZvcm1hdGlvbiBhYm91dCB0aW1lc3RhbXBzIGdpdmVuIGJ5IHRoZSBzdW1tYXJ5IHNob3dzIHRoYXQgdGhlIHJhdGluZ3MgYXJlIHJlbGF0ZWQgdG8gdGhlIHllYXJzIDE5OTggdG8gMjAxNCwgYnV0IHRoZSBtYWpvcml0eSBpcyBiZXR3ZWVuIDIwMTEgYW5kIDIwMTQuCgokfiQKCkFmdGVyIEkgaGFkIGFuIG92ZXJ2aWV3IG9mIGRhdGEsIEkgaW1tZWRpYXRlbHkgY2hlY2sgZm9yIHRoZSAqKnByZXNlbmNlIG9mIE5BIHZhbHVlcyoqLCB0aGF0IGNvdWxkIGNyZWF0ZSBwcm9ibGVtcyB3aGVuIGNvbXB1dGluZyBzdGF0aXN0aWNzIG9uIGRhdGEgYW5kIHRoYXQsIGlmIHByZXNlbnQsIGhhdmUgdG8gYmUgc3Vic3RpdHV0ZWQgd2l0aCByZWFsIHZhbHVlcyBvciBvbWl0dGVkLgpgYGB7ciByYXRpbmcgTkEgdmFsdWVzIGNoZWNrfQp0X2NvdW50ID0gc3VtKGlzLm5hKGRzKSkKaXNfbmEgPSBpZiAodF9jb3VudCA+IDApICdUaGUgcmF0aW5ncyBkYXRhc2V0IGRvZXMgY29udGFpbiBOQSB2YWx1ZXMnIGVsc2UgJ1RoZSByYXRpbmdzIGRhdGFzZXQgZG9lcyBub3QgY29udGFpbiBOQSB2YWx1ZXMnCmNhdChpc19uYSkKYGBgCmBgYHtyIG1ldGFkYXRhIE5BIHZhbHVlcyBjaGVja30KdF9jb3VudCA9IHN1bShpcy5uYShtZXRhZGF0YSkpCmlzX25hID0gaWYgKHRfY291bnQgPiAwKSAnVGhlIG1ldGFkYXRhIGRhdGFzZXQgZG9lcyBjb250YWluIE5BIHZhbHVlcycgZWxzZSAnVGhlIG1ldGFkYXRhIGRhdGFzZXQgZG9lcyBub3QgY29udGFpbiBOQSB2YWx1ZXMnCmNhdChpc19uYSkKYGBgCkFzIEkgYWxyZWFkeSBtZW50aW9uZWQgYmVmb3JlLCB3aGlsZSB0aGUgcmF0aW5ncyBkYXRhc2V0IGRvZXMgbm90IGNvbnRhaW4gTkEgdmFsdWVzLCB0aGUgbWV0YWRhdGEgZGF0YXNldCBjb250YWlucyBOQSB2YWx1ZXMsIGJ1dCBpbiBvcmRlciB0byBmaW5kIGFsbCBvZiB0aGVtLCB3ZSBuZWVkIHRvIHNlYXJjaCBhbHNvIGluc2lkZSB0aGUgbGlzdHMgb2Ygc29tZSBhdHRyaWJ1dGUuIFRvIGRvIHNvLCBJIHdpbGwgY2hlY2sgb25seSB0aGUgYXR0cmlidXRlcyB0aGF0IGNvdWxkIGJlIHVzZWZ1bCBmb3IgdGhlIGNvbnN0cnVjdGlvbiBvZiBhIHJlY29tbWVuZGF0aW9uIHN5c3RlbSAoZm9yIGV4YW1wbGUsIEkgZGlzY2FyZCB0aGUgKmRlc2NyaXB0aW9uKiBpbiBhZHZhbmNlKS4KCmBgYHtyIG1ldGFkYXRhIGF0dHJpYnV0ZXMgTkEgdmFsdWVzIGNoZWNrfQojIC0tIGFzaW4gTkEgdmFsdWVzIGNoZWNrCgl0X2NvdW50ID0gc3VtKGlzLm5hKG1ldGFkYXRhJGFzaW4pKQoJaXNfbmEgPSBpZiAodF9jb3VudCA+IDApICdUaGUgYXR0cmlidXRlIGFzaW4gZG9lcyBjb250YWluIE5BIHZhbHVlcycgZWxzZSAnVGhlIGF0dHJpYnV0ZSBhc2luIGRvZXMgbm90IGNvbnRhaW4gTkEgdmFsdWVzJwoJY2F0KGlzX25hLCAiXG4iKQojIC0tIHNhbGVzUmFuayBOQSB2YWx1ZXMgY2hlY2sKCSMgcHJpbnQobmFtZXMobWV0YWRhdGEkc2FsZXNSYW5rKSkJCQkjIHByaW50IGFsbCB0aGUgZGlmZmVyZW50IGNhdGVnb3JpZXMgb2Ygc2FsZXMgcmFuawoJdF9jb3VudCA9IHN1bShpcy5uYShtZXRhZGF0YSRzYWxlc1JhbmskYE11c2ljYWwgSW5zdHJ1bWVudHNgKSkKCWlzX25hID0gaWYgKHRfY291bnQgPiAwKSAnVGhlIGF0dHJpYnV0ZSBNdXNpY2FsIEluc3RydW1lbnRzIHNhbGVzUmFuayBkb2VzIGNvbnRhaW4gTkEgdmFsdWVzJyBlbHNlICdUaGUgYXR0cmlidXRlIE11c2ljYWwgSW5zdHJ1bWVudHMgc2FsZXNSYW5rIGRvZXMgbm90IGNvbnRhaW4gTkEgdmFsdWVzJwoJY2F0KGlzX25hLCAiLT4iLCB0X2NvdW50LCAib3ZlciIsIGxlbmd0aChtZXRhZGF0YSRzYWxlc1JhbmskYE11c2ljYWwgSW5zdHJ1bWVudHNgKSwgIlxuIikKIyAtLSByZWxhdGVkIE5BIHZhbHVlcyBjaGVjawoJbmV3X3JlbGF0ZWQgPSBtZXRhZGF0YSRyZWxhdGVkCgluZXdfcmVsYXRlZFtuZXdfcmVsYXRlZCA9PSAiTlVMTCJdID0gTkEJCQkJIyBjb252ZXJ0IE5VTEwgdmFsdWVzIGluIE5BIHZhbHVlcwoJbl92YWx1ZXMgPSBucm93KG1ldGFkYXRhJHJlbGF0ZWQpKm5jb2wobWV0YWRhdGEkcmVsYXRlZCkKCXRfY291bnQgPSBzdW0oaXMubmEodW5saXN0KG5ld19yZWxhdGVkKSkpCglpc19uYSA9IGlmICh0X2NvdW50ID4gMCkgJ1RoZSBhdHRyaWJ1dGUgcmVsYXRlZCBkb2VzIGNvbnRhaW4gTkEgdmFsdWVzJyBlbHNlICdUaGUgYXR0cmlidXRlIHJlbGF0ZWQgZG9lcyBub3QgY29udGFpbiBOQSB2YWx1ZXMnCgljYXQoaXNfbmEsICItPiIsIHRfY291bnQsICJvdmVyIiwgbl92YWx1ZXMsICJcbiIpCiMgLS0gYnJhbmQgTkEgdmFsdWVzIGNoZWNrCgluX3ZhbHVlcyA9IGxlbmd0aChtZXRhZGF0YSRicmFuZCkKCXRfY291bnQgPSBzdW0oaXMubmEobWV0YWRhdGEkYnJhbmQpKQoJaXNfbmEgPSBpZiAodF9jb3VudCA+IDApICdUaGUgYXR0cmlidXRlIGJyYW5kIGRvZXMgY29udGFpbiBOQSB2YWx1ZXMnIGVsc2UgJ1RoZSBhdHRyaWJ1dGUgYnJhbmQgZG9lcyBub3QgY29udGFpbiBOQSB2YWx1ZXMnCgljYXQoaXNfbmEsICItPiIsIHRfY291bnQsICJvdmVyIiwgbl92YWx1ZXMsICJcbiIpCiMgLS0gcHJpY2UgTkEgdmFsdWVzIGNoZWNrCgluX3ZhbHVlcyA9IGxlbmd0aChtZXRhZGF0YSRwcmljZSkKCXRfY291bnQgPSBzdW0oaXMubmEobWV0YWRhdGEkcHJpY2UpKQoJaXNfbmEgPSBpZiAodF9jb3VudCA+IDApICdUaGUgYXR0cmlidXRlIHByaWNlIGRvZXMgY29udGFpbiBOQSB2YWx1ZXMnIGVsc2UgJ1RoZSBhdHRyaWJ1dGUgcHJpY2UgZG9lcyBub3QgY29udGFpbiBOQSB2YWx1ZXMnCgljYXQoaXNfbmEsICItPiIsIHRfY291bnQsICJvdmVyIiwgbl92YWx1ZXMpCgpgYGAKClVuZm9ydHVuYXRlbHksIHRoZSBudW1iZXIgb2YgTkEgdmFsdWVzIGZvciAqTXVzaWNhbCBJbnN0cnVtZW50cyBzYWxlcyByYW5rKiwgKnJlbGF0ZWQqIGFuZCAqYnJhbmQqIGlzIHRvbyBoaWdoOiBpbiB0aGUgZmlyc3QgYXR0cmlidXRlIGEgcXVhcnRlciBvZiB0aGUgdmFsdWVzIGFyZSBtaXNzaW5nLCB3aGlsZSBpbiB0aGUgb3RoZXIgdHdvIG1vcmUgdGhhbiBhbiBoYWxmIG9mIHRoZSB2YWx1ZXMgYXJlIE5BLiBGb3IgdGhpcyByZWFzb24sIGl0IHdvdWxkIGJlIHBvaW50bGVzcyB0byB0cnkgdG8gc3Vic3RpdHV0ZSB0aGUgTkEgdmFsdWVzIHdpdGggdGhlIG1lYW4gb2YgdGhlIHByZXNlbnQgdmFsdWVzLCBvciB0byBkZWxldGUgdGhlIGRhdGEgd2l0aCBOQSB2YWx1ZXMgZnJvbSB0aGUgZGF0YXNldC4gVGhlcmVmb3JlLCBJIHRoaW5rIGluIHRoaXMgY2FzZSBpdCBpcyBhcHByb3ByaWF0ZSBub3QgdG8gY29uc2lkZXIgdGhlc2UgYXR0cmlidXRlcyBmb3IgdGhlIGRldmVsb3BtZW50IG9mIHRoZSByZWNvbW1lbmRhdGlvbiBzeXN0ZW1zLgoKSG93ZXZlciwgYXMgcmVnYXJkcyB0aGUgbnVtYmVyIG9mIE5BIHZhbHVlcyBmb3IgdGhlIGF0dHJpYnV0ZSAqcHJpY2UqLCBpdCBpcyBib3JkZXJsaW5lIGFuZCBJIHdpbGwgZGVjaWRlIGxhdGVyIGlmIGl0IGNvdWxkIGJlIHVzZWZ1bCB0byBhbmFseXNlIGl0LgoKJH4kCgpUbyBiZSBzaHVyZSB0aGF0IEkgY2FuIHVzZSBhbGwgdGhlIGl0ZW1zIGZvciB0aGUgY29uc3RydWN0aW9uIG9mIG15IHJlY29tbWVuZGF0aW9uIHN5c3RlbSwgSSBjaGVjayBpZiBhbGwgb2YgdGhlbSBjb250YWluIHRoZSBjYXRlZ29yeSAiTXVzaWNhbCBJbnN0cnVtZW50cyIgYW1vbmcgdGhlIGNhdGVnb3JpZXMuCmBgYHtyIE11c2ljYWwgSW5zdHJ1bWVudHMgY2F0ZWdvcnkgY2hlY2t9CiMgLS0gUHJpbnQgdW5pcXVlIHBvc3NpYmxlIHZhbHVlcyBmb3IgYXR0cmlidXRlIGNhdGVnb3JpZXMKCSMgcHJpbnQodW5pcXVlKHVubGlzdChtZXRhZGF0YSRjYXRlZ29yaWVzKSkpCiMgLS0gQWxsIHRoZSBsaXN0cyBpbnRlcm5hbCB0byBjYXRlZ29yaWVzIGFyZSBmbGF0dGVuCglmb3IgKGkgaW4gbGVuZ3RoKG1ldGFkYXRhJGNhdGVnb3JpZXMpKSB7CgkJdGVtcCA9IHVubGlzdChtZXRhZGF0YSRjYXRlZ29yaWVzW2ldKQoJCW1ldGFkYXRhJGNhdGVnb3JpZXNbW2ldXSA9IHRlbXAKCX0KIyAtLSBDaGVjayBpZiBhbGwgdGhlIGl0ZW1zIGhhdmUgIk11c2ljYWwgSW5zdHJ1bWVudHMiIGFzIG9uZSBvZiB0aGVpciBjYXRlZ29yaWVzCgljaGVjayA9IG1ldGFkYXRhW2lzLmVsZW1lbnQoIk11c2ljYWwgSW5zdHJ1bWVudHMiLCBtZXRhZGF0YSRjYXRlZ29yaWVzKV0KCWNhdCgiSXRlbXMgb2YgdGhlIGRhdGFmcmFtZSB0aGF0IGhhdmUgJ011c2ljYWwgSW5zdHJ1bWVudHMnIGluIHRoZWlyIGNhdGVnb3JpZXM6IiwgbnJvdyhjaGVjayksICJvdmVyIiwgbnJvdyhtZXRhZGF0YSkpCmBgYAoKCiMjIFJlcHJlc2VudGF0aW9uIGFuZCB2aXN1YWxpemF0aW9uIG9mIGRhdGEKCkluIG9yZGVyIHRvIGV4cGxvcmUgYW5kIGRlc2NyaWJlIGRhdGEsIEkgYWxzbyB1c2Ugc29tZSAqKmdyYXBoaWMgcmVwcmVzZW50YXRpb25zKiosIHRoYXQgY2FuIHNob3cgdGhlIGRhdGEgZGlzdHJpYnV0aW9uIGFuZCBzb21lIG9mIGl0cyBjaGFyYWN0ZXJpc3RpY3MuCgpJIHN0YXJ0IGJ5IGJsb3R0aW5nIGFuIGhpc3RvZ3JhbSBzaG93aW5nIHRoZSByZWxhdGl2ZSBmcmVxdWVuY2llcyBvZiByYXRpbmdzLgpgYGB7ciBIaXN0b2dyYW0gb2YgcmF0aW5nc30KZ2dwbG90KGRhdGE9ZHMsIGFlcyh4PXJhdGluZywgZmlsbD1yYXRpbmcpKSArCiAgICBnZW9tX2JhcihmaWxsPSJzdGVlbGJsdWUiLCBhZXMoeT0uLmNvdW50Li4vc3VtKC4uY291bnQuLikpKSArCgkJc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cyA9IGMoMCwxKSkgKwoJCWxhYnModGl0bGUgPSAiSGlzdG9ncmFtIG9mIHJhdGluZ3MiLCB4ID0gIlJhdGluZyIsIHkgPSAiUmVsYXRpdmUgZnJlcXVlbmN5IikgKwoJCXRoZW1lX21pbmltYWwoKQpmciA9IHByb3AudGFibGUodGFibGUoZHMkcmF0aW5nKSkKZnIgPSBwZXJjZW50KGZyKQpwcmludChmcikKYGBgClRoZSBmaWd1cmUgc2hvd3MgdGhhdCB0aGVyZSBpcyBhIGxhcmdlIG1ham9yaXR5IG9mIGhpZ2ggcmF0aW5nczogbW9yZSB0aGFuIGEgaGFsZiBvZiB0aGUgcmF0aW5ncyBhcmUgZXF1YWwgdG8gNS4gVGhpcyBjb25maXJtcyB0aGUgcHJldmlvdXMgY29uc2lkZXJhdGlvbnMgcmVzdWx0aW5nIGZyb20gdGhlIGRlc2NyaXB0aXZlIHN0YXRpc3RpY3MuCgokfiQKClRoZSBmb2xsb3dpbmcgcGxvdCBzaG93cyB0aGUgdHJlbmQgb2YgdGhlIHJhdGluZydzIG1lYW4gYXMgdGhlIHllYXJzIHBhc3NlZC4KYGBge3IgUmF0aW5ncyBtZWFuIHdydCB5ZWFyc30KbV9ieV95ID0gYWdncmVnYXRlKGRzJHJhdGluZywgbGlzdCh5ZWFyKGRzJHRpbWVzdGFtcCkpLCBtZWFuKQpjb2xuYW1lcyhtX2J5X3kpID0gYygieWVhcnMiLCAibWVhbnMiKQojIHByaW50KG1fYnlfeSkKZ2dwbG90KGRhdGE9bV9ieV95LCBhZXMoeD15ZWFycywgeT1tZWFucywgZmlsbD15ZWFycykpICsKICAgIGdlb21fYmFyKHN0YXQgPSAiaWRlbnRpdHkiLCBmaWxsPSJzdGVlbGJsdWUiKSArCgkJc2NhbGVfeF9jb250aW51b3VzKGxpbWl0cyA9IGMobWluKG1fYnlfeSR5ZWFycyktMSxtYXgobV9ieV95JHllYXJzKSsxKSwgCgkJCQkJCQkJCQkJIGJyZWFrcyA9IGMobWluKG1fYnlfeSR5ZWFycyksMjAwMCwyMDA1LDIwMTAsbWF4KG1fYnlfeSR5ZWFycykpKSArCgkJc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cyA9IGMoMCw1KSkgKwoJCWdlb21faGxpbmUoYWVzKHlpbnRlcmNlcHQ9bWVhbihtX2J5X3kkbWVhbnMpLCBsaW5ldHlwZSA9ICJUb3RhbCBtZWFuIiksIGNvbG91cj0iZGFya2JsdWUiKSArCgkJc2NhbGVfbGluZXR5cGVfbWFudWFsKG5hbWUgPSAiTGVnZW5kIiwgdmFsdWVzID0gYygyLCAyKSkgKwoJCWxhYnModGl0bGUgPSAiVHJlbmQgb2YgcmF0aW5nJ3MgbWVhbiBiYXNlZCBvbiB5ZWFycyIsIHggPSAiWWVhcnMiLCB5ID0gIlJhdGluZydzIG1lYW4iKSArCgkJdGhlbWVfbWluaW1hbCgpCmBgYAoKJH4kCgpTaW5jZSB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IGl0ZW1zIHRoYXQgaGF2ZSBiZWVuIHJhdGVkIGlzIHZlcnkgYmlnICg4MywwNDUpLCBpbiBvcmRlciB0byB2aXN1YWxpemUgdGhlIGRpc3RyaWJ1dGlvbiBvZiByYXRpbmcgd2l0aCByZXNwZWN0IHRvIHRoZSBpdGVtcyBJIGRlY2lkZWQgdG8gcmVwcmVzZW50IHRoZSBpdGVtcycgcmF0aW5ncyBpbiB0aGUgcGxvdCBieSAxNyBvcmRlcmVkIGdyb3VwcyBvZiA0ODg1IGl0ZW1zIGVhY2gsIHNvIHRoYXQgYSBjbGVhcmVyIGdyYXBoIGlzIG9idGFpbmVkLiBUaGUgZmlndXJlIHNob3dzIHRoZSByYXRpbmcsIGFnZ3JlZ2F0ZWQgYnkgbWVhbiwgZm9yIGVhY2ggZ3JvdXAgb2YgaXRlbXMuCmBgYHtyIFJhdGluZyBtZWFuIHdydCBpdGVtc30KbV9ieV95ID0gYWdncmVnYXRlKGRzJHJhdGluZywgbGlzdChkcyRpdGVtKSwgbWVhbikKY29sbmFtZXMobV9ieV95KSA9IGMoIml0ZW1zIiwgIm1lYW5zIikKbV9ieV95ID0gbV9ieV95W3dpdGgobV9ieV95LCBvcmRlcihtX2J5X3kkbWVhbnMsIGRlY3JlYXNpbmcgPSBUUlVFKSksXQpncm91cHMgPSBjKHJlcCgiRyIsIDE3KSkKZ3JvdXBzID0gcGFzdGUoZ3JvdXBzLCBjKDE6MTcpLCBzZXAgPSAiIikKCnYgPSBjKCkKaSA9IDEKTiA9IDQ4ODUKZm9yIChrIGluIDE6MTcpIHsKCXZba10gPSBtZWFuKG1fYnlfeSRtZWFuc1tpOihpK04tMSldKQoJaSA9IGkrTgp9CgpkZiA9IGRhdGEuZnJhbWUoImdyb3VwcyIgPSBncm91cHMsCgkJCQkJCQkJICJtZWFucyIgPSB2LAoJCQkJCQkJCSBzdHJpbmdzQXNGYWN0b3JzID0gRkFMU0UpCmRmJGdyb3VwcyA8LSBmYWN0b3IoZGYkZ3JvdXBzLCBsZXZlbHMgPSBkZiRncm91cHMpCmdncGxvdChkYXRhPWRmLCBhZXMoeD1ncm91cHMsIHk9bWVhbnMsIGZpbGw9Z3JvdXBzKSkgKwogICAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIpICsKCQlzY2FsZV95X2NvbnRpbnVvdXMobGltaXRzID0gYygwLDUpKSArCgkJZ2VvbV9obGluZShhZXMoeWludGVyY2VwdD1tZWFuKG1fYnlfeSRtZWFucyksIGxpbmV0eXBlID0gIlRvdGFsIG1lYW4iKSwgY29sb3VyPSJkYXJrYmx1ZSIpICsKCQlzY2FsZV9saW5ldHlwZV9tYW51YWwobmFtZSA9ICJMZWdlbmQiLCB2YWx1ZXMgPSBjKDIsIDIpKSArCgkJc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzPWMocmVwKCJzdGVlbGJsdWUiLCAxNykpKSArCgkJZ3VpZGVzKGZpbGw9RkFMU0UpICsKCQlsYWJzKHRpdGxlID0gIlJhdGluZydzIG1lYW4gd2l0aCByZXNwZWN0IHRvIGl0ZW1zIiwgeCA9ICJJdGVtcyIsIHkgPSAiUmF0aW5nJ3MgbWVhbiIpICsKCQl0aGVtZV9taW5pbWFsKCkKCmBgYAoKSXQgY291bGQgYmUgYWxzbyBpbnRlcmVzdGluZyB0byBzZWUgdGhlIHJlbGF0aW9uIGJldHdlZW4gdGhlIHJhdGluZ3MgYW5kIHRoZSBwcmljZXMgb2YgaXRlbXMuIFRvIG9idGFpbiBpdCwgSSBkaXNjYXJkIGZyb20gdGhlIG1ldGFkYXRhIGRhdGFzZXQgYWxsIHRoZSBpdGVtcyB0aGF0IGhhdmVuJ3QgYmVlbiByYXRlZCBhbmQgZnJvbSBib3RoIHRoZSBkYXRhc2V0cyBhbGwgdGhlIGl0ZW1zIHRoYXQgaGF2ZSB0aGUgcHJpY2UgdmFsdWUgZXF1YWwgdG8gTkEuIFRoZW4sIEkgY29tcHV0ZSB0aGUgY29ycmVsYXRpb24gbWF0cml4IGJldHdlZW4gdGhlIHJhdGluZ3MgYW5kIHRoZSBwcmljZXMgdG8gY2hlY2sgZm9yIHRoZSBwcmVzZW5jZSBvZiBhIGxpbmVhciBjb3JyZWxhdGlvbiBiZXR3ZWVuIGRhdGEgYW5kIEkgYWxzbyBwbG90IHRoZSBkaXN0cmlidXRpb24gb2YgdGhlIHR3byByZWxhdGVkIHZhcmlhYmxlIHRvIGhhdmUgYW4gb3ZlcmFsbCB2aWV3IGFuZCB0byBjaGVjayBmb3IgdGhlIHByZXNlbmNlIG9mIG5vbi1saW5lYXIgcmVsYXRpb25zLgoKYGBge3IgQ29ycmVsYXRpb24gYmV0d2VlbiByYXRpbmcgYW5kIHByaWNlfQojIC0tIERpc2NhcmQgZnJvbSBtZXRhZGF0YSBhbGwgdGhlIGl0ZW1zIHRoYXQgaGF2ZW4ndCBiZWVuIHJhdGVkCm1ldGFkYXRhID0gbWV0YWRhdGFbaXMuZWxlbWVudChtZXRhZGF0YSRhc2luLCBkcyRpdGVtKSxdCiMgLS0gRGlzY2FyZCBmcm9tIGJvdGggdGhlIGRhdGFzZXQgYWxsIHRoZSBpdGVtcyB0aGF0IGhhdmUgdGhlIHByaWNlIHZhbHVlIGVxdWFsIHRvIE5BCm1ldGFkYXRhX3ByaWNlID0gbWV0YWRhdGFbIWlzLm5hKG1ldGFkYXRhJHByaWNlKSxdCm1ldGFkYXRhX3ByaWNlID0gZGF0YS5mcmFtZSgiYXNpbiIgPSBtZXRhZGF0YV9wcmljZSRhc2luLAoJCQkJCQkJCSAJCQkJCQkicHJpY2UiID0gbWV0YWRhdGFfcHJpY2UkcHJpY2UsCgkJCQkJCQkJIAkJCQkJCXN0cmluZ3NBc0ZhY3RvcnMgPSBGQUxTRSkKbWV0YWRhdGFfcHJpY2UgPSBtZXRhZGF0YV9wcmljZVtvcmRlcihtZXRhZGF0YV9wcmljZSRhc2luKSxdCmRzX3ByaWNlID0gZHNbaXMuZWxlbWVudChkcyRpdGVtLCBtZXRhZGF0YV9wcmljZSRhc2luKSxdCmRzX3ByaWNlID0gYWdncmVnYXRlKGRzX3ByaWNlJHJhdGluZywgYnkgPSBsaXN0KGRzX3ByaWNlJGl0ZW0pLCBtZWFuKQpkc19wcmljZSA9IGRzX3ByaWNlW29yZGVyKGRzX3ByaWNlJEdyb3VwLjEpLF0KZHNfcHJpY2UgPSBkYXRhLmZyYW1lKCJpdGVtIiA9IGRzX3ByaWNlJEdyb3VwLjEsCgkJCQkJCQkJCQkJInByaWNlIiA9IG1ldGFkYXRhX3ByaWNlJHByaWNlLAoJCQkJCQkJCSAJCQkicmF0aW5nIiA9IGRzX3ByaWNlJHgsCgkJCQkJCQkJIAkJCXN0cmluZ3NBc0ZhY3RvcnMgPSBGQUxTRSkKbWVhbnMgPSBhZ2dyZWdhdGUoZHNfcHJpY2UkcHJpY2UsIGJ5ID0gbGlzdChkc19wcmljZSRyYXRpbmcpLCBtZWFuKQpuYW1lcyhtZWFucykgPSBjKCJyYXRpbmciLCAicHJpY2UiKQpjb3JtYXQgPSByb3VuZChjb3IobWVhbnMpLCA0KQpjb3JtYXQKCmdncGxvdChkYXRhID0gbWVhbnMsIGFlcyh4ID0gcmF0aW5nLCB5ID0gcHJpY2UpKSArIAogIGdlb21fcG9pbnQoY29sb3I9J3N0ZWVsYmx1ZScpICsKCXRoZW1lX21pbmltYWwoKQoKYGBgCgpUaGUgcmVzdWx0aW5nIGNvcnJlbGF0aW9uIG1hdHJpeCBzaG93cyB0aGF0IHRoZXJlIGlzIG5vIGxpbmVhciBjb3JyZWxhdGlvbiBiZXR3ZWVuIHRoZSB2YXJpYWJsZXMgKnJhdGluZyogYW5kICpwcmljZSosIGFzIHRoZSBjb3JyZWxhdGlvbiB2YWx1ZSBpcyB2ZXJ5IGNsb3NlIHRvIHplcm8uIEhvd2V2ZXIsIGZyb20gdGhlIGdyYXBoIHdlIGNhbiBkZWR1Y3QgdGhlIHByZXNlbmNlIG9mIGEgbm9uLWxpbmVhciByZWxhdGlvbiBiZXR3ZWVuIHRoZSB0d28gdmFyaWFibGVzOiBhcyB0aGUgcmF0aW5ncyBncm93cywgYWxzbyB0aGUgcHJpY2VzIGdyb3dzLCBidXQgaXQgaXMgYWxzbyB0cnVlIHRoYXQgYSBsb3Qgb2YgaXRlbXMgd2l0aCBoaWdoIHJhdGluZyBoYXZlIGEgdmVyeSBsb3cgcHJpY2UgYW5kIHRoZSBoaWdoZXIgdGhlIHJhdGluZywgdGhlIGRlbnNlciBpcyB0aGUgImNsb3VkIiBvZiBsb3cgcHJpY2VzLgoKIyMgUHJlLXByb2Nlc3Npbmcgb2YgZGF0YQoKSW4gb3JkZXIgdG8gY3JlYXRlIHRoZSByZWNvbW1lbmRhdGlvbiBzeXN0ZW1zLCBJIHdpbGwgdXNlIG9ubHkgdGhlIHJhdGluZ3MgZGF0YXNldCwgYmVjYXVzZSB0aGUgbWV0YWRhdGEgZGF0YXNldCBjb250YWlucyB0b28gbWFueSBOQSB2YWx1ZXMuIEkgcmVtb3ZlIHRoZSBhdHRyaWJ1dGUgKnRpbWVzdGFtcCogZnJvbSB0aGUgcmF0aW5ncyBkYXRhc2V0IHNpbmNlIEkgZG9uJ3QgbmVlZCBpdC4KYGBge3IgRGF0YWZyYW1lIHJhdGluZ30KcmF0aW5nID0gZHNbLGMoInVzZXIiLCAiaXRlbSIsICJyYXRpbmciKV0KYGBgCgpJIHdpbGwgdXNlIGEgKipzdWJzZXQgb2YgdXNlcnMgYW5kIGl0ZW1zKiogdG8gY3JlYXRlIHRoZSByZWNvbW1lbmRhdGlvbiBzeXN0ZW1zIGZvciB0d28gcmVhc29uczoKCiogVXNpbmcgYWxsIHRoZSBkYXRhIHdvdWxkIGJlIHZlcnkgZXhwZW5zaXZlIGluIHRlcm1zIG9mIGNvbXB1dGF0aW9uYWwgY29zdCwgdGhlcmVmb3JlLCByZWR1Y2luZyBkYXRhIGRpbWVuc2lvbmFsaXR5LCBJIGNhbiBzcGVlZCB1cCB0aGUgY29tcHV0YXRpb247CiogTW9zdCBvZiB0aGUgdXNlcnMgYXBwZWFyIGluIG9ubHkgb25lIHJhdGluZywgc28gSSB3aWxsIGtlZXAgb25seSB0aGUgdXNlcnMgdGhhdCBhcHBlYXIgaW4gNiBvciBtb3JlIHJhdGluZ3MgaW4gb3JkZXIgdG8gcmVkdWNlIHRoZSBzcGFyc2l0eSBvZiB0aGUgdXRpbGl0eSBtYXRyaXg7IGZvciB0aGUgc2FtZSByZWFzb24sIEkgd2lsbCBrZWVwIG9ubHkgdGhlIGl0ZW1zIHRoYXQgaGF2ZSBiZWVuIHJhdGVkIDIwIG9yIG1vcmUgdGltZXMuCgpgYGB7ciBEYXRhc2V0IGZpbHRlcmluZ30KIyAtLSBDaGVjayBpZiBlYWNoIHVzZXIgcmF0ZWQgZWFjaCBpdGVtcyBvbmx5IG9uY2UKIyBsZW5ndGgodW5pcXVlKGMoZHMkdXNlciwgZHMkaXRlbSkpKQkJCSMgbnVtYmVyIG9mIGRpc3RpbmN0IGNvdXBsZXMgInVzZXIsIGl0ZW0iIGVxdWFscyBudW1iZXIgb2YgZGlzdGluY3QgdXNlcnMKb2xkX25yb3cgPSBucm93KHJhdGluZykKIyAtLSBNZWFuIG9mIHRoZSBudW1iZXIgb2YgcmF0aW5ncyByZWNlaXZlZCBieSBlYWNoIGl0ZW0KaXRlbV9yYXRpbmcgPSBhZ2dyZWdhdGUocmF0aW5nJHJhdGluZywgYnkgPSBsaXN0KHJhdGluZyRpdGVtKSwgbGVuZ3RoKQpuYW1lcyhpdGVtX3JhdGluZykgPSBjKCJpdGVtIiwgIm5yYXRpbmciKQppdGVtX21lYW4gPSBtZWFuKGl0ZW1fcmF0aW5nJG5yYXRpbmcpCQkJIyBpdGVtX21lYW4gPSA2LjAyMwpvbGRfbnJvd19pdGVtID0gbnJvdyhpdGVtX3JhdGluZykKIyAtLSBJdGVtcyBmaWx0ZXJpbmcKaXRlbV9yYXRpbmcgPSBpdGVtX3JhdGluZ1tpdGVtX3JhdGluZyRucmF0aW5nID49IDIwLF0KcmF0aW5nID0gcmF0aW5nW2lzLmVsZW1lbnQocmF0aW5nJGl0ZW0sIGl0ZW1fcmF0aW5nJGl0ZW0pLF0KIyAtLSBNZWFuIG9mIHRoZSBudW1iZXIgb2YgcmF0aW5ncyBkb25lIGJ5IGVhY2ggdXNlcgp1c2VyX3JhdGluZyA9IGFnZ3JlZ2F0ZShyYXRpbmckcmF0aW5nLCBieSA9IGxpc3QocmF0aW5nJHVzZXIpLCBsZW5ndGgpCm5hbWVzKHVzZXJfcmF0aW5nKSA9IGMoInVzZXIiLCAibnJhdGluZyIpCnVzZXJfbWVhbiA9IG1lYW4odXNlcl9yYXRpbmckbnJhdGluZykJCQkJIyB1c2VyX21lYW4gPSAxLjQ3Cm9sZF9ucm93X3VzZXIgPSBucm93KHVzZXJfcmF0aW5nKQojIC0tIFVzZXJzIGZpbHRlcmluZwp1c2VyX3JhdGluZyA9IHVzZXJfcmF0aW5nW3VzZXJfcmF0aW5nJG5yYXRpbmcgPj0gNixdCnJhdGluZyA9IHJhdGluZ1tpcy5lbGVtZW50KHJhdGluZyR1c2VyLCB1c2VyX3JhdGluZyR1c2VyKSxdCmNhdCgiU3Vic2V0IG9mIHJhdGluZyAtPiAiLCAiVG90YWwgbnVtYmVyIG9mIHJhdGluZ3M6IiwgbnJvdyhyYXRpbmcpLCAib3ZlciIsIG9sZF9ucm93LCAiXG4iLAoJCSJcdFx0XHRcdFx0IiwgIk51bWJlciBvZiBkaXN0aW5jdCB1c2VyczoiLCBsZW5ndGgodW5pcXVlKHJhdGluZyR1c2VyKSksICJvdmVyIiwgb2xkX25yb3dfdXNlciwgIlxuIiwKCQkiXHRcdFx0XHRcdCIsICJOdW1iZXIgb2YgZGlzdGluY3QgaXRlbXM6IiwgbGVuZ3RoKHVuaXF1ZShyYXRpbmckaXRlbSkpLCAib3ZlciIsIG9sZF9ucm93X2l0ZW0sICJcbiIpCmBgYApUaGUgcmVzdWx0aW5nIGRhdGFzZXQgY29udGFpbnMgMTUsODY0IHJhdGluZ3MsIDEsODQwIGRpc3RpbmN0IHVzZXJzIGFuZCAzLDE0NyBkaXN0aW5jdCBpdGVtcy4gVGhpcyB3aWxsIGJlIHRoZSBkYXRhc2V0IG9uIHdoaWNoIEkgd2lsbCB3b3JrIGZyb20gbm93IG9uLgoKCiMjIFJlY29tbWVuZGF0aW9uIHN5c3RlbXMKCkluIG9yZGVyIHRvIGJ1aWxkIHRoZSB0d28gcmVjb21tZW5kYXRpb24gc3lzdGVtcyByZXF1aXJlZCBieSB0aGUgcHJvamVjdCwgSSdtIGdvaW5nIHRvIHVzZSAqKmNvbGxhYm9yYXRpdmUgZmlsdGVyaW5nKiogKENGKSBpbiBib3RoIGNhc2VzOiBvbmUgb2YgdGhlbSB3aWxsIG1ha2UgdXNlIG9mIHRoZSAqdXNlci1iYXNlZCBjb2xsYWJvcmF0aXZlIGZpbHRlcmluZyogKGBVQkNGYCksIHRoZSBvdGhlciB3aWxsIG1ha2UgdXNlIG9mIHRoZSAqaXRlbS1iYXNlZCBjb2xsYWJvcmF0aXZlIGZpbHRlcmluZyogKGBJQkNGYCkuCgpDb2xsYWJvcmF0aXZlIGZpbHRlcmluZyBpcyBhbiBhbGdvcml0aG0gdGhhdCB1c2VzIGdpdmVuIHJhdGluZyBkYXRhIGJ5IG1hbnkgdXNlcnMgZm9yIG1hbnkgaXRlbXMgYXMgdGhlIGJhc2lzIGZvciBwcmVkaWN0aW5nIG1pc3NpbmcgcmF0aW5ncyBvciBmb3IgY3JlYXRpbmcgYSBsaXN0IG9mIGl0ZW1zIHdpdGggdGhlIHRvcC1OIGl0ZW1zIHRvIHJlY29tbWVuZCB0byBhIGdpdmVuIHVzZXIsIGNhbGxlZCB0aGUgYWN0aXZlIHVzZXIuIFRoZSBkYXRhIGFyZSBvcmdhbml6ZWQgaW4gYSAkbSBcdGltZXMgbiQgdXNlci1pdGVtIG1hdHJpeCwgY2FsbGVkICp1dGlsaXR5IG1hdHJpeCogb3IgKnNwYXJzZSBtYXRyaXgqLCB3aGVyZSBlYWNoIHJvdyByZXByZXNlbnRzIGEgdXNlciBhbmQgZWFjaCBjb2x1bW4gcmVwcmVzZW50cyBhbiBpdGVtLiBJbnRvIGVhY2ggdXNlci1pdGVtIGNlbGwgaXQgaXMgc3RvcmVkIHRoZSByYXRpbmcgb2YgdGhhdCB1c2VyIGZvciB0aGF0IGl0ZW0uIFVzdWFsbHksIHRoZSB1dGlsaXR5IG1hdHJpeCBpcyB2ZXJ5IHNwYXJzZSwgYmVjYXVzZSBvbmx5IGEgc21hbGwgZnJhY3Rpb24gb2YgcmF0aW5ncyBhcmUga25vd24sIHNvIG1vc3Qgb2YgdGhlIGNlbGxzIG9mIHRoZSBtYXRyaXggY29udGFpbiBOQSB2YWx1ZXMuCgpUd28gb2YgdGhlIG1haW4gY2F0ZWdvcmllcyBvZiBDRiBhbGdvcml0bXMgYXJlIHRoZSB1c2VyLWJhc2VkIGNvbGxhYm9yYXRpdmUgZmlsdGVyaW5nIGFuZCB0aGUgaXRlbS1iYXNlZCBjb2xsYWJvcmF0aXZlIGZpbHRlcmluZy4gVGhlIGBVQkNGYCBhbGdvcml0aG1zIGJhc2VzIHRoZSByZWNvbW1lbmRhdGlvbnMgb24gdGhlIHNpbWlsYXJpdHkgYmV0d2VlbiB1c2VyczogdGhlIGFzc3VtcHRpb24gaXMgdGhhdCB1c2VycyB3aXRoIHNpbWlsYXIgcHJlZmVyZW5jZXMgd2lsbCByYXRlIGl0ZW1zIHNpbWlsYXJseS4gRWFjaCB1c2VyIGlzIHJlcHJlc2VudGVkIGJ5IGhpcyByb3cgb2YgcmF0aW5ncyBpbiB0aGUgdXRpbGl0eSBtYXRyaXgsIHNvLCBpbiBvcmRlciB0byBjb21wdXRlIHRoZSBzaW1pbGFyaXR5IGJldHdlZW4gdXNlcnMsIHdlIG5lZWQgdG8gYXBwbHkgYSBzaW1pbGFyaXR5IG1lYXN1cmUgKGZvciBpc3RhbmNlLCB0aGUgKmNvc2luZSBzaW1pbGFyaXR5KikgYmV0d2VlbiB0aGUgcm93IG9mIHRoZSBhY3RpdmUgdXNlciBhbmQgYWxsIHRoZSBvdGhlciByb3dzLiBJbiB0aGlzIHdheSwgd2UgY2FuIGZpbmQgdGhlIG1vc3Qgc2ltaWxhciB1c2VycyBhbmQgdXNlIHRoZWlyIHJhdGluZ3MgaW4gdHdvIHdheXM6CgoqIFRoZSBsaXN0IG9mIGJlc3QgcmF0ZWQgaXRlbXMgb2YgdGhlIHNpbWlsYXIgdXNlcnMgY2FuIGJlIHVzZWQgdG8gbWFrZSByZWNvbW1lbmRhdGlvbnMgdG8gdGhlIGFjdGl2ZSB1c2VyOwoqIFRoZSBtaXNzaW5nIHJhdGluZyBvZiB0aGUgYWN0aXZlIHVzZXIgY2FuIGJlIHByZWRpY3RlZCBieSBhZ2dyZWdhdGluZyB0aGUgcmF0aW5ncyBvZiB0aGUgc2ltaWxhciB1c2VycyB0byBmb3JtIGEgcHJlZGljdGlvbi4KClRoZSBgSUJDRmAgYWxnb3JpdGhtcyBiYXNlcyB0aGUgcmVjb21tZW5kYXRpb25zIG9uIHRoZSBzaW1pbGFyaXR5IGJldHdlZW4gaXRlbXM6IHRoZSBhc3N1bXB0aW9uIGlzIHRoYXQgdXNlcnMgd2lsbCBwcmVmZXIgaXRlbXMgdGhhdCBhcmUgc2ltaWxhciB0byBvdGhlciBpdGVtcyB0aGV5IGxpa2UuIEVhY2ggaXRlbSBpcyByZXByZXNlbnRlZCBieSBoaXMgY29sdW1uIG9mIHJhdGluZ3MgaW4gdGhlIHV0aWxpdHkgbWF0cml4LCBzbywgaW4gb3JkZXIgdG8gY29tcHV0ZSB0aGUgc2ltaWxhcml0eSBiZXR3ZWVuIGl0ZW1zLCB3ZSBuZWVkIHRvIGFwcGx5IGEgc2ltaWxhcml0eSBtZWFzdXJlIChmb3IgaXN0YW5jZSwgdGhlICpjb3NpbmUgc2ltaWxhcml0eSopIGJldHdlZW4gYWxsIHRoZSBjb2x1bW5zIG9mIHRoZSB1dGlsaXR5IG1hdHJpeC4gSW4gdGhpcyB3YXksIHdlIGNhbiBidWlsZCBhICRuIFx0aW1lcyBuJCBpdGVtLWl0ZW0gc2ltaWxhcml0eSBtYXRyaXggY29udGFpbmluZyB0aGUgc2ltaWxhcml0eSB2YWx1ZXMgZm9yIGVhY2ggaXRlbXMgY291cGxlLiBUbyByZWR1Y2UgdGhlIGRpbWVuc2lvbmFsaXR5IG9mIHRoZSBzaW1pbGFyaXR5IG1hdHJpeCwgaW5zdGVhZCB3ZSBjb3VsZCBidWlsZCBhICRuIFx0aW1lcyBrJCBpdGVtLWl0ZW0gc2ltaWxhcml0eSBtYXRyaXggY29udGFpbmluZywgZm9yIGVhY2ggaXRlbSwgdGhlIHNpbWlsYXJpdHkgdmFsdWVzIG9mIG9ubHkgdGhlIGsgbW9zdCBzaW1pbGFyIGl0ZW1zLiBGcm9tIHRoZSBzaW1pbGFyaXR5IG1hdHJpeCwgd2UgY2FuIHVzZSB0aGUgaXRlbXMgdGhhdCBhcmUgdGhlIG1vc3Qgc2ltaWxhciB0byB0aGUgYmVzdCByYXRlZCBpdGVtcyBvZiB0aGUgYWN0aXZlIHVzZXIgaW4gb3JkZXIgdG8gb2J0YWluOgoKKiBBIGxpc3Qgb2Ygc2ltaWxhciBpdGVtcyB0byBtYWtlIHJlY29tbWVuZGF0aW9ucyB0byB0aGUgYWN0aXZlIHVzZXI7CiogVGhlIG1pc3NpbmcgcmF0aW5nIG9mIHRoZSBhY3RpdmUgdXNlciBieSBhZ2dyZWdhdGluZyB0aGUgcmF0aW5ncyBvZiB0aGUgc2ltaWxhciBpdGVtcyB0byBmb3JtIGEgcHJlZGljdGlvbi4KCiR+JAoKSW4gb3JkZXIgdG8gYnVpbGQgdGhlIHR3byByZWNvbWVuZGF0aW9uIHN5c3RlbXMsIEknbSBnb2luZyB0byB1c2UgdGhlICpyZWNvbW1lbmRlcmxhYiogbGlicmFyeSwgd2hpY2ggcHJvdmlkZXMgc2V2ZXJhbCBhbGdvcml0aG1zIGZvciB0aGlzIHRpcGUgb2YgdGFzayB0aGF0IGFyZSBhbHJlYWR5IGltcGxlbWVudGVkLgoKRmlyc3QsIEkgbmVlZCB0byBjcmVhdGUgdGhlICoqdXRpbGl0eSBtYXRyaXgqKiBmcm9tIHRoZSByYXRpbmdzIGRhdGFzZXQuIFRoZSBmdW5jdGlvbiBgZGNhc3RgIGlzIHBlcmZlY3QgZm9yIHRoaXMgcHVycG9zZTogaXQgc2ltcGx5IHN0b3JlcyB0aGUgdXNlcnMgYXMgcm93cycgaW5kaWNlcywgdGhlIGl0ZW1zIGFzIGNvbHVtbnMnIGluZGljZXMgYW5kIHRoZSByYXRpbmdzIGFzIHZhbHVlcyBpbnNpZGUgdGhlIHVzZXItaXRlbSBjZWxscy4KCmBgYHtyIFV0aWxpdHkgbWF0cml4IGNyZWF0aW9ufQp1dGlsaXR5X21hdHJpeCA9IGRjYXN0KHJhdGluZywgZm9ybXVsYSA9IHVzZXJ+aXRlbSwgdmFsdWUudmFyID0gJ3JhdGluZycpCmBgYAoKYGBge3IgVXRpbGl0eSBtYXRyaXggdmFsdWVzfQpuX3ZhbHVlcyA9IG5yb3codXRpbGl0eV9tYXRyaXgpKihuY29sKHV0aWxpdHlfbWF0cml4KS0xKQkJIyB0aGUgZmlyc3QgY29sdW1uIGNvbnRhaW5zIHVzZXJzJ2lkcwpyZWFsX3ZhbHVlcyA9IHN1bSghaXMubmEodXRpbGl0eV9tYXRyaXhbLC0xXSkpCmNhdCgiTnVtYmVyIG9mIHJlYWwgcmF0aW5nIHZhbHVlczoiLCByZWFsX3ZhbHVlcywgIm92ZXIiLCBuX3ZhbHVlcykKYGBgClRoZSB1dGlsaXR5IG1hdHJpeCBjb250YWlucyA1LDc5MCw0ODAgdmFsdWVzLCBvZiB3aGljaCBvbmx5IDE1LDg2NCBhcmUgcmVhbCByYXRpbmdzIGFuZCB0aGUgb3RoZXJzIGFyZSBtaXNzaW5nIHZhbHVlcyAoTkEpLgoKQmVmb3JlIHdvcmtpbmcgb24gdGhlIHV0aWxpdHkgbWF0cml4LCBJIG5lZWQgdG8gY29udmVydCBpdCBpbnRvIGBtYXRyaXhgIHR5cGUgKHRoZSBmdW5jdGlvbiBgZGNhc3RgIHJldHVybnMgYSBsaXN0KSBpbiBvcmRlciB0byBiZSBhYmxlIHRvIHRyYW5zZm9ybSBpdCBpbiBhIGByZWFsUmF0aW5nTWF0cml4YCB0byBoYW5kbGUgaXQgdGhyb3VnaCB0aGUgKnJlY29tbWVudGRlcmxhYiogbGlicmFyeS4KYGBge3IgVXRpbGl0eSBtYXRyaXggdG8gcmVhbFJhdGluZ01hdHJpeH0KbSA9IGFzLm1hdHJpeCh1dGlsaXR5X21hdHJpeFssLTFdKQpyb3duYW1lcyhtKSA9IHV0aWxpdHlfbWF0cml4WywxXQojIHByaW50KG1bMToxMCwxOjhdKQp1dGlsaXR5X20gPC0gYXMobSwgInJlYWxSYXRpbmdNYXRyaXgiKQp1dGlsaXR5X20KYGBgCgpCZWZvcmUgYnVpbGRpbmcgdGhlIGFjdHVhbCByZWNvbW1lbmRhdGlvbiBzeXN0ZW1zLCBJIGNyZWF0ZSBhbiAqKmV2YWx1YXRpb24gc2NoZW1lKiogdGhhdCBkZXRlcm1pbmVzIHdoYXQgYW5kIGhvdyBkYXRhIGlzIHVzZWQgZm9yIHRyYWluaW5nIGFuZCB0ZXN0aW5nIGFuZCB0aGF0IGFsbG93cyBtZSB0byBldmFsdWF0ZSB0aGUgdHdvIG1vZGVscyBhdCB0aGUgZW5kLiBUaGUgZGl2aXNpb24gaW4gdHJhaW5pbmcgc2V0IGFuZCB0ZXN0IHNldCBtYWtlcyBpdCBwb3NzaWJsZSB0byBwcmVkaWN0IHRoZSByYXRpbmdzIG9mIHRoZSB1c2VycyBpbiB0aGUgdGVzdCBzZXQgdXNpbmcgdGhlIHRyYWluaW5nIHNldC4gVGhyb3VnaCB0aGUgZXZhbHVhdGlvbiBzY2hlbWUsIEkgc3BsaXQgdGhlIGRhdGFzZXQgdXNpbmcgNzUlIG9mIHVzZXJzIGZvciB0aGUgdHJhaW5pbmcgc2V0IGFuZCAyNSUgZm9yIHRoZSB0ZXN0IHNldCwgSSBjb25zaWRlciBnb29kIHJhdGluZ3Mgb25seSB0aGUgcmF0aW5ncyBlcXVhbCB0byA1IChhbnl3YXksIG1vcmUgdGhhbiBhIGhhbGYgb2YgdGhlIHJhdGluZ3MgYXJlIGVxdWFsIHRvIDUpIGFuZCBJIHNldCB0byA0IHRoZSB2YWx1ZSBvZiBnaXZlbiByYXRpbmdzLCBzbyB0aGF0IGluIHRoZSB0ZXN0IHNldCBlYWNoIHVzZXIgaGF2ZSA0IHJhdGluZ3MgZ2l2ZW4gYW5kIHRoZSByZWNvbW1lbmRhdGlvbiBzeXN0ZW1zIGhhdmUgdG8gcHJlZGljdCB0aGUgb3RoZXJzIHRoYXQgYXJlIG1pc3NpbmcuCmBgYHtyIEV2YWx1YXRpb24gU2NoZW1lfQplID0gZXZhbHVhdGlvblNjaGVtZSh1dGlsaXR5X20sIG1ldGhvZCA9ICJzcGxpdCIsIHRyYWluID0gMC43NSwgZ2l2ZW4gPSA0LCBnb29kUmF0aW5nID0gNSkKZQpgYGAKCkFmdGVyIHRoYXQsIEkgY3JlYXRlIHRoZSB0d28gcmVjb21tZW5kYXRpb24gc3lzdGVtcyB3aXRoIHRoZSBmdW5jdGlvbiBgUmVjb21tZW5kZXJgLCB3aGVyZSBJIGNhbiBzZXQgdGhlIHRyYWluaW5nIHNldCBhcyB0aGUgZGF0YSB0aGF0IGl0IGhhcyB0byB1c2UgdG8gYnVpbGQgdGhlIHJlY29tbWVuZGF0aW9uIHN5c3RlbSBhbmQgdGhlIG1ldGhvZCwgZGVwZW5kaW5nIG9uIHdoZXRoZXIgaXQgaGFzIHRvIHVzZSB0aGUgYFVCQ0ZgIG9yIHRoZSBgSUJDRmAuIFRoZW4sIEkgdXNlIHRoZSBjcmVhdGVkIGBSZWNvbW1lbmRlcnNgIGluIG9yZGVyIHRvIHByZWRpY3QgdGhlIG1pc3NpbmcgcmF0aW5ncyBpbiB0aGUgdGVzdCBzZXQgdGhyb3VnaCB0aGUgZnVuY3Rpb24gYHByZWRpY3RgLgoKYGBge3IgUmVjb21tZW5kZXIgY3JlYXRpb24gYW5kIHByZWRpY3Rpb259CiMgLS0tIFJlY29tbWVuZGF0aW9uIHN5c3RlbSB1c2luZyBVQkNGCnJVQkNGID0gUmVjb21tZW5kZXIoZ2V0RGF0YShlLCAidHJhaW4iKSwgbWV0aG9kID0gIlVCQ0YiKQpyVUJDRgpwVUJDRiA9IHByZWRpY3QoclVCQ0YsIGdldERhdGEoZSwgImtub3duIiksIHR5cGUgPSAicmF0aW5ncyIpCnBVQkNGCiMgLS0tIFJlY29tbWVuZGF0aW9uIHN5c3RlbSB1c2luZyBJQkNGCnJJQkNGID0gUmVjb21tZW5kZXIoZ2V0RGF0YShlLCAidHJhaW4iKSwgbWV0aG9kID0gIklCQ0YiKQpySUJDRgpwSUJDRiA9IHByZWRpY3QocklCQ0YsIGdldERhdGEoZSwgImtub3duIiksIHR5cGUgPSAicmF0aW5ncyIpCnBJQkNGCmBgYAoKRmluYWxseSwgSSBldmFsdWF0ZSB0aGUgcHJlZGljdGlvbnMgb2YgdGhlIHR3byByZWNvbW1lbmRhdGlvbiBzeXN0ZW1zIGJ5IGNvbXBhcmluZyB0aGVpciBhY2N1cmFjeSB0aHJvdWdoIGFuIGV2YWx1YXRpb24gbWF0cml4LiBUaGUgbWF0cml4IGNvbnRhaW5zLCBmb3IgZWFjaCBtb2RlbCwgdGhlICpyb290LW1lYW4tc3F1YXJlIGVycm9yIChSTVNFKSosIHRoYXQgaXMgdGhlIHNxdWFyZSByb290IG9mIHRoZSBtZWFuIHNxdWFyZSBlcnJvciwgdGhlICptZWFuIHNxdWFyZWQgZXJyb3IgKE1TRSkqLCB0aGF0IG1lYXN1cmVzIHRoZSBhdmVyYWdlIG9mIHRoZSBzcXVhcmVzIG9mIHRoZSBkaWZmZXJlbmNlcyBiZXR3ZWVuIHByZWRpY3RlZCB2YWx1ZXMgYW5kIG9ic2VydmVkIHZhbHVlcywgYW5kIHRoZSAqbWVhbiBhYnNvbHV0ZSBlcnJvciAoTUFFKSosIHRoYXQgcmVwcmVzZW50cyB0aGUgYXZlcmFnZSBhYnNvbHV0ZSBkaWZmZXJlbmNlIGJldHdlZW4gcHJlZGljdGVkIHZhbHVlcyBhbmQgb2JzZXJ2ZWQgdmFsdWVzLgoKYGBge3IgTW9kZWxzIGV2YWx1YXRpb259CiMgRXJyb3IgYmV0d2VlbiBwcmVkaWN0aW9uIGFuZCB1bmtub3duIHBhcnQgb2YgdGhlIHRlc3QgZGF0YQplcnJvciA9IHJiaW5kKFVCQ0YgPSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHBVQkNGLCBnZXREYXRhKGUsICJ1bmtub3duIikpLAoJCQkJCQkJSUJDRiA9IGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocElCQ0YsIGdldERhdGEoZSwgInVua25vd24iKSkpCmVycm9yCmBgYAoKSSB0cmllZCBkaWZmZXJlbnQgY29uZmlndXJhdGlvbnMgZm9yIHRoZSBkYXRhIGZpbHRlcmluZywgbG93ZXJpbmcgb3IgcmFzaW5nIHRoZSBudW1iZXIgb2YgdXNlcnMgYW5kIGl0ZW1zIHNlbGVjdGVkIHRvIGZvcm0gdGhlIGRhdGFzZXQ6IG9idmlvdXNseSwgdGhlIGhpZ2hlciB0aGUgbWluaW11bSBudW1iZXIgb2YgcmF0aW5ncyBmb3IgZWFjaCB1c2VyIGFuZCBpdGVtLCB0aGUgbG93ZXIgdGhlIGVycm9yIG9mIHRoZSBwcmVkaWN0aW9ucy4KSW4gZ2VuZXJhbCwgdGhlIGBVQkNGYCB3b3JrcyBiZXR0ZXIgdGhhbiB0aGUgYElCQ0ZgIHdpdGggZXZlcnkgY29uZmlndXJhdGlvbiBJIHRyaWVkLCBzaW5jZSBhbGwgdGhlIHRocmVlIG1lYXN1cmVzIG9mIGVycm9yIGFyZSBoaWdoZXIgaW4gdGhlIGBVQkNGYCB0aGFuIGluIHRoZSBgSUJDRmAuCgoKCgoKCgoK